題目連結: Climbing Stairs

題目描述為: 距離樓梯頂部有 N 階，而每一次我們可走的步長為 1 階及 2 階，
問爬到樓梯頂部共有幾種方法?

例子 1: N=2, ans=2。 ( 1+1, 2 共2種方法)
例子 2: N=3, ans=3。 (1+1+1, 1+2, 2+1 共3種方法)

思路 1: 動態規劃法

根據題目描述，設 K>2，我們可以推論到達第 K 階的方法只有 2 種: 從第 K-1 階行走1步上來，以及從第 K-2 階行走2步上來。因此我們可以得到公式: 設 f(K)表示到達第 K 階的方法，則 f(K)=f(K-1)+f(K-2)。此形式與day07-Fibonacci Number一致。我們將採用 day07 提到的方法 3: 迭代法來解此問題。

• 複雜度評估
  當要求第 N 項時，我們需要從頭開始累加 N 次，時間複雜度為 O(N)。
  此方法只用了常數量變數，與 N 無關，空間複雜度為 O(1)。

參考程式碼

func climbStairs(n int) int {
    
    if n<=2{
        return n
    }
    
    first:=1
    second:=2
    sum:=0
  
    
    for i:=3;i<=n;i++{
        sum=first+second
        first=second
        second=sum      
    }
    
    return sum
}

小結:

方法 1 為著名的動態規劃法，核心思想為將原問題分解為多個子問題依次求解，而每次子問題的解也對後一個子問題的求解有所幫助。費式數列求第 N 項過程即可分解成依次求第 1 項到第 N 項的過程。另一例子為求 N 階乘 (1x2x3x..xN)，我們也可以分解為依次求 1 階乘到 N 階乘。此方法相當實用，空間複雜度也低，之後會再補充相關應用題目。
我將解法加上簡單的測試，上傳程式碼到此。